//+------------------------------------------------------------------+
//|                                                      HashSet.mqh |
//|                             Copyright 2000-2025, MetaQuotes Ltd. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#include<Generic\Interfaces\ISet.mqh>                // 继承集合接口 ISet<T>，获取基础集合能力
#include <Generic/Internal/PrimeGenerator.h>          // 质数生成工具，用于优化哈希表容量（减少冲突）
#include <Generic/Interfaces/IEqualityComparer.h>     // 相等性比较器接口，支持自定义元素相等逻辑
#include <Generic/Internal/DefaultEqualityComparer.h> // 默认相等性比较器，适配基础类型

//+------------------------------------------------------------------+
//| Slot<T> 结构体：CHashSet 内部存储单元                            |
//| 核心定位：哈希集合的底层元素存储结构，封装元素的哈希码、值及链表指针 |
//| 用途：用于哈希表的“桶（Bucket）”与链表存储，解决哈希冲突          |
//+------------------------------------------------------------------+
template<typename T>
struct Slot
  {
public:
   int               hash_code;        // 元素的哈希码（用于快速定位桶）
   T                 value;            // 存储的元素值（唯一，集合特性）
   int               next;             // 链表指针（指向同一桶内下一个元素的索引，解决冲突）

   /**
    * @brief 默认构造函数：初始化哈希码为0、元素值为空、链表指针为0
    */
                     Slot(void) : hash_code(0), value((T)NULL), next(0) {}
  };

//+------------------------------------------------------------------+
//| CHashSet<T> 类：哈希集合实现类                                   |
//| 核心定位：实现 ISet<T> 接口，基于哈希表实现“元素唯一”的集合，支持高效元素操作 |
//| 核心特性：                                                      |
//|  1. 元素唯一性：同一元素仅能存储一次，重复添加会失败；            |
//|  2. 高效操作：添加/删除/查找时间复杂度接近 O(1)（哈希表特性）；    |
//|  3. 冲突处理：通过链表法解决哈希冲突（同一桶内元素形成链表）；     |
//|  4. 集合运算：支持差集、交集、并集等数学集合操作（继承 ISet 接口）；|
//| 适用场景：所有需要管理唯一元素且需高效增删查的场景（如订单ID去重、权限标识集合、数据去重） |
//+------------------------------------------------------------------+
template<typename T>
class CHashSet : public ISet<T>
  {
protected:
   int               m_buckets[];      // 哈希桶数组（存储链表头索引，每个桶对应一组哈希冲突元素）
   Slot<T>           m_slots[];        // 元素存储数组（所有元素的实际存储位置，含链表指针）
   int               m_count;          // 当前集合中的有效元素数量（≥0，空集合为0）
   int               m_last_index;     // 元素存储数组的最后一个使用索引（用于扩容时定位有效元素）
   int               m_free_list;      // 空闲项链表头（复用已删除元素的存储位置，减少内存分配）
   IEqualityComparer<T>* m_comparer;   // 元素相等性比较器（判断两个元素是否相同）
   bool              m_delete_comparer;// 是否自动释放比较器内存（构造时传入外部比较器则为false）

public:
   //----------------------------------------------------------------
   // 构造与析构接口
   //----------------------------------------------------------------
   /**
    * @brief 默认构造函数：创建空集合，使用默认元素相等性比较器
    * @note 默认比较器为 CDefaultEqualityComparer<T>，适配基础类型（int/double/string等）
    */
                     CHashSet(void);

   /**
    * @brief 指定比较器构造函数：创建空集合，使用自定义元素相等性比较器
    * @param comparer [in] 元素相等性比较器（实现 IEqualityComparer<T> 接口）
    * @note 适用于自定义元素类型（如结构体/类），需自定义相等判断逻辑（如按特定字段比较）
    */
                     CHashSet(IEqualityComparer<T>* comparer);

   /**
    * @brief 从集合构造函数：创建集合并复制指定集合的所有元素，使用默认比较器
    * @param collection [in] 源集合（实现 ICollection<T> 接口，如 ArrayList/HashSet）
    * @note 自动去重（源集合中的重复元素仅保留一个），初始容量适配源集合元素数量
    */
                     CHashSet(ICollection<T>* collection);

   /**
    * @brief 集合+比较器构造函数：创建集合并复制指定集合的所有元素，使用自定义比较器
    * @param collection [in] 源集合（实现 ICollection<T> 接口）
    * @param comparer [in] 元素相等性比较器（实现 IEqualityComparer<T> 接口）
    */
                     CHashSet(ICollection<T>* collection, IEqualityComparer<T>* comparer);

   /**
    * @brief 从数组构造函数：创建集合并复制指定数组的所有元素，使用默认比较器
    * @param array [in] 源数组（元素类型与 T 一致）
    * @note 自动去重（数组中的重复元素仅保留一个），初始容量适配数组长度
    */
                     CHashSet(T &array[]);

   /**
    * @brief 数组+比较器构造函数：创建集合并复制指定数组的所有元素，使用自定义比较器
    * @param array [in] 源数组（元素类型与 T 一致）
    * @param comparer [in] 元素相等性比较器（实现 IEqualityComparer<T> 接口）
    */
                     CHashSet(T &array[], IEqualityComparer<T>* comparer);

   /**
    * @brief 析构函数：清理集合资源
    * @note 若比较器为内部创建（使用默认比较器），则自动释放比较器内存；外部传入的比较器需手动管理
    */
                    ~CHashSet(void);

   //----------------------------------------------------------------
   // 元素添加接口
   //----------------------------------------------------------------
   /**
    * @brief 向集合中添加元素（仅当元素不存在时添加成功）
    * @param value [in] 待添加的元素（类型与 T 一致）
    * @return bool - 添加结果：true=添加成功（元素不存在）；false=添加失败（元素已存在）
    * @note 核心集合特性：保证元素唯一性，内部通过哈希码+比较器判断元素是否存在
    */
   bool              Add(T value);

   //----------------------------------------------------------------
   // 基础信息与包含性检查接口
   //----------------------------------------------------------------
   /**
    * @brief 获取集合中的有效元素数量
    * @return int - 元素数量（≥0，空集合返回0）
    */
   int               Count(void) { return(m_count); }

   /**
    * @brief 获取当前使用的元素相等性比较器
    * @return IEqualityComparer<T>* - 比较器实例（NULL 表示未设置）
    */
   IEqualityComparer<T>* Comparer(void) const { return(m_comparer); }

   /**
    * @brief 检查集合是否包含指定元素
    * @param item [in] 待检查的元素（类型与 T 一致）
    * @return bool - 检查结果：true=元素存在；false=元素不存在
    * @note 内部逻辑：通过元素哈希码定位桶，再遍历桶内链表查找，效率接近 O(1)
    */
   bool              Contains(T item);

   /**
    * @brief 缩减集合容量至实际元素数量（释放未使用的内存）
    * @note 适用于元素数量大幅减少后（如批量删除后），将容量调整为“能容纳当前元素的最小质数”，减少内存浪费
    */
   void              TrimExcess(void);

   //----------------------------------------------------------------
   // 批量复制接口
   //----------------------------------------------------------------
   /**
    * @brief 将集合中的所有元素复制到外部数组
    * @param dst_array [out] 目标数组（需提前分配空间，或由方法自动扩容）
    * @param dst_start [in] 目标数组的起始复制索引（默认从0开始）
    * @return int - 实际复制的元素数量（等于 Count()）
    * @note 复制顺序不保证与添加顺序一致（哈希表存储特性）
    */
   int               CopyTo(T &dst_array[], const int dst_start=0);

   //----------------------------------------------------------------
   // 清理与删除接口
   //----------------------------------------------------------------
   /**
    * @brief 清空集合中的所有元素（释放内存，重置状态）
    * @note 清空后容量重置为0，元素数量为0，空闲项链表清空
    */
   void              Clear(void);

   /**
    * @brief 从集合中删除指定元素
    * @param item [in] 待删除的元素（类型与 T 一致）
    * @return bool - 删除结果：true=删除成功（元素存在）；false=删除失败（元素不存在）
    * @note 删除后元素对应的存储位置加入空闲链表，可被后续添加复用
    */
   bool              Remove(T item);

   //----------------------------------------------------------------
   // 集合运算接口（继承自 ISet<T>，实现数学意义上的集合操作）
   //----------------------------------------------------------------
   /**
    * @brief 差集运算：从当前集合中移除与目标集合共有的元素（当前集合 = 当前集合 - 交集）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @example 当前集合={1,2,3}，目标集合={2,3,4} → 结果={1}
    */
   void              ExceptWith(ICollection<T>* collection);

   /**
    * @brief 差集运算：从当前集合中移除与目标数组共有的元素（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    */
   void              ExceptWith(T &array[]);

   /**
    * @brief 交集运算：保留当前集合与目标集合的共有元素（当前集合 = 交集）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @example 当前集合={1,2,3}，目标集合={2,3,4} → 结果={2,3}
    */
   void              IntersectWith(ICollection<T>* collection);

   /**
    * @brief 交集运算：保留当前集合与目标数组的共有元素（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    */
   void              IntersectWith(T &array[]);

   /**
    * @brief 对称差集运算：保留仅在当前集合或目标集合中存在的元素（当前集合 = (A-B)∪(B-A)）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @example 当前集合={1,2,3}，目标集合={2,3,4} → 结果={1,4}
    */
   void              SymmetricExceptWith(ICollection<T>* collection);

   /**
    * @brief 对称差集运算：保留仅在当前集合或目标数组中存在的元素（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    */
   void              SymmetricExceptWith(T &array[]);

   /**
    * @brief 并集运算：合并当前集合与目标集合的所有元素（去重，当前集合 = A∪B）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @example 当前集合={1,2,3}，目标集合={2,3,4} → 结果={1,2,3,4}
    */
   void              UnionWith(ICollection<T>* collection);

   /**
    * @brief 并集运算：合并当前集合与目标数组的所有元素（去重，参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    */
   void              UnionWith(T &array[]);

   //----------------------------------------------------------------
   // 集合关系判断接口（继承自 ISet<T>，验证集合间的包含/相等关系）
   //----------------------------------------------------------------
   /**
    * @brief 判断当前集合是否为目标集合的真子集（A⊂B 且 A≠B）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @return bool - 判断结果：true=是真子集；false=不是
    * @note 真子集要求：当前集合所有元素都在目标集合中，且目标集合元素数量更多
    */
   bool              IsProperSubsetOf(ICollection<T>* collection);

   /**
    * @brief 判断当前集合是否为目标数组的真子集（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    * @return bool - 判断结果
    */
   bool              IsProperSubsetOf(T &array[]);

   /**
    * @brief 判断当前集合是否为目标集合的真超集（A⊃B 且 A≠B）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @return bool - 判断结果：true=是真超集；false=不是
    * @note 真超集要求：目标集合所有元素都在当前集合中，且当前集合元素数量更多
    */
   bool              IsProperSupersetOf(ICollection<T>* collection);

   /**
    * @brief 判断当前集合是否为目标数组的真超集（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    * @return bool - 判断结果
    */
   bool              IsProperSupersetOf(T &array[]);

   /**
    * @brief 判断当前集合是否为目标集合的子集（A⊆B，可与目标集合相等）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @return bool - 判断结果：true=是子集；false=不是
    * @note 子集要求：当前集合所有元素都在目标集合中（允许两者元素数量相同）
    */
   bool              IsSubsetOf(ICollection<T>* collection);

   /**
    * @brief 判断当前集合是否为目标数组的子集（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    * @return bool - 判断结果
    */
   bool              IsSubsetOf(T &array[]);

   /**
    * @brief 判断当前集合是否为目标集合的超集（A⊇B，可与目标集合相等）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @return bool - 判断结果：true=是超集；false=不是
    * @note 超集要求：目标集合所有元素都在当前集合中（允许两者元素数量相同）
    */
   bool              IsSupersetOf(ICollection<T>* collection);

   /**
    * @brief 判断当前集合是否为目标数组的超集（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    * @return bool - 判断结果
    */
   bool              IsSupersetOf(T &array[]);

   /**
    * @brief 判断当前集合与目标集合是否存在交集（是否有共同元素）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @return bool - 判断结果：true=存在交集；false=无交集
    */
   bool              Overlaps(ICollection<T>* collection);

   /**
    * @brief 判断当前集合与目标数组是否存在交集（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    * @return bool - 判断结果
    */
   bool              Overlaps(T &array[]);

   /**
    * @brief 判断当前集合与目标集合是否完全相等（元素完全相同，忽略顺序）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @return bool - 判断结果：true=元素完全相同；false=存在差异
    * @note 相等判定条件：元素数量相同 + 所有元素互相包含
    */
   bool              SetEquals(ICollection<T>* collection);

   /**
    * @brief 判断当前集合与目标数组是否完全相等（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    * @return bool - 判断结果
    */
   bool              SetEquals(T &array[]);

private:
   //----------------------------------------------------------------
   // 内部辅助接口（不对外暴露，仅用于实现核心逻辑）
   //----------------------------------------------------------------
   /**
    * @brief 调整集合容量并重新计算哈希（内部扩容/缩容时调用）
    * @param new_size [in] 新容量（需为质数，由 PrimeGenerator 生成）
    * @param new_hash_codes [in] 是否重新计算所有元素的哈希码（true=重新计算；false=沿用旧值）
    * @note 扩容时会重建哈希桶结构，确保元素均匀分布，减少冲突
    */
   void              SetCapacity(const int new_size, bool new_hash_codes);

   /**
    * @brief 仅当元素不存在时添加（内部统一添加逻辑，被 Add() 调用）
    * @param value [in] 待添加的元素
    * @return bool - 添加结果：true=添加成功；false=元素已存在
    */
   bool              AddIfNotPresent(T value);

   /**
    * @brief 初始化集合容量（创建哈希桶和存储数组）
    * @param capacity [in] 初始容量（实际会调整为最近的质数，优化哈希分布）
    */
   void              Initialize(const int capacity);

   /**
    * @brief 内部对称差集实现（针对 CHashSet 类型的目标集合，优化性能）
    * @param set [in] 目标哈希集合（CHashSet<T> 实例）
    */
   void              InternalSymmetricExceptWith(CHashSet<T>* set);

   /**
    * @brief 内部子集判断（针对 CHashSet 类型的目标集合，优化性能）
    * @param set [in] 目标哈希集合（CHashSet<T> 实例）
    * @return bool - 判断结果：true=是子集；false=不是
    */
   bool              InternalIsSubsetOf(CHashSet<T>* set);

   /**
    * @brief 内部超集判断（针对 CHashSet 类型的目标集合，优化性能）
    * @param set [in] 目标哈希集合（CHashSet<T> 实例）
    * @return bool - 判断结果：true=是超集；false=不是
    */
   bool              InternalIsSupersetOf(CHashSet<T>* set);

   /**
    * @brief 内部真子集判断（针对 CHashSet 类型的目标集合，优化性能）
    * @param set [in] 目标哈希集合（CHashSet<T> 实例）
    * @return bool - 判断结果：true=是真子集；false=不是
    */
   bool              InternalIsProperSubsetOf(CHashSet<T>* set);

   /**
    * @brief 内部真超集判断（针对 CHashSet 类型的目标集合，优化性能）
    * @param set [in] 目标哈希集合（CHashSet<T> 实例）
    * @return bool - 判断结果：true=是真超集；false=不是
    */
   bool              InternalIsProperSupersetOf(CHashSet<T>* set);
  };
//+------------------------------------------------------------------+